import java.util.ArrayList;
import java.util.List;

public class Solution655 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    int deep=0;

    public List<List<String>> printTree(TreeNode root) {
        dfs1(root,0);
        List<List<String>> list=new ArrayList<>();
        dfs2(root,0,list);
        int t=0;
        for (int i=list.size()-1;i>=0;i--){
            List<String> temp=new ArrayList<>();
            for (int j=0;j<t;j++){
                temp.add("");
            }
            for (int j=0;j<list.get(i).size();j++){
                temp.add(list.get(i).get(j));
                for (int k=0;k<2*t+1;k++){
                    temp.add("");
                }
            }
            for (int j=0;j<t+1;j++){
                temp.remove(temp.size()-1);
            }
            t=2*t+1;
            list.set(i,temp);
        }
        return list;
    }

    private void dfs2(TreeNode root, int d,List<List<String>> lists) {
        if (d>deep){
            return;
        }
        if (lists.size()==d){
            lists.add(new ArrayList<>());
        }
        lists.get(d).add(root==null?"":String.valueOf(root.val));
        dfs2(root==null?null:root.left,d+1,lists);
        dfs2(root==null?null:root.right,d+1,lists);
    }

    private void dfs1(TreeNode root, int d) {
        if (root==null){
            return;
        }
        if (d>deep){
            deep=d;
        }
        dfs1(root.left,d+1);
        dfs1(root.right,d+1);
    }

    public static void main(String[] args) {
        System.out.println(new Solution655().printTree(new TreeNode(1,new TreeNode(2,null,new TreeNode(4)),new TreeNode(3))));
    }
}
